package syf.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
//        int[] arr={1,8,10,89,1000,1000,1000,1000,1000,1234};
        int[] arr=new int[100];
        for (int i=0;i<arr.length;i++ ) {
            arr[i] = i;
        }
//        int i = binarySearch(arr, 0, arr.length, 1234);
        int i = binarySearch2(arr, 0, arr.length-1, 10);
//        List<Integer>arrayList=binarySearch3(arr, 0, arr.length-1,1000);
        System.out.println(i);
//        System.out.println(arrayList);
    }

    /**
     * 二分查找，必须有序
     * @param arr 有序的数组
     * @param value 要查找的内容
     * @return 返回查找内容在数组中的下标，没有找到就返回-1
     */
    public static int binarySearch(int[] arr,int left,int right,int value){
        //中间值的下标
        int mid=(left+right)/2;
        //被查询的数组左边开始下标
        int l=left;
        //被查询数组的右边开始下边
        int r=mid+1;
        //如果要查询的值大于中间值，往右边查
        if (value>arr[mid]){
            //当左边下标小于右边时继续查找
            while (r<right){
                //找到直接返回
                if (value==arr[r]){
                    return r;
                }
                r++;
            }
        }//如果要查询的值小于中间值，往左边查
        else if (value<arr[mid]){
            while (l<r){
                //找到直接返回
                if (value==arr[l]){
                    return l;
                }
                l++;
            }
        }//如果相等，已经找到直接返回
        else {
            return mid;
        }//如果以上都没结束，表示没有找到
        return -1;
    }
    /**
     * 二分查找，必须有序
     * @param arr 有序的数组
     * @param value 要查找的内容
     * @return 返回查找内容在数组中的下标，没有找到就返回-1
     * 递归方式
     */
    public static int binarySearch2(int[] arr,int left,int right,int value){
        System.out.println("===");
        if (right<left)
            return -1;
        //中间值的下标
        int mid=(left+right)/2;
        //被查询数组的右边开始下边
        //如果要查询的值大于中间值，往右边查
        if (value>arr[mid]){
            //当左边下标小于右边时继续查找
            return binarySearch2(arr,mid+1,right,value);
        }//如果要查询的值小于中间值，往左边查
        else if (value<arr[mid]){
            return binarySearch2(arr, left,mid-1,value);
        }//如果相等，已经找到直接返回
        else{
            return mid;
        }
    }

    /**
     * 查找所有，其余和上面的一样
     * @param arr
     * @param left
     * @param right
     * @param value
     * @return
     */
    public static List<Integer> binarySearch3(int[] arr, int left, int right, int value){
        List<Integer> arrayList=new ArrayList<>();
        if (right<left)
            return arrayList;
        int tmp;
        //中间值的下标
        int mid=(left+right)/2;
        //被查询数组的右边开始下边
        //如果要查询的值大于中间值，往右边查
        if (value>arr[mid]){
            //当左边下标小于右边时继续查找
            return binarySearch3(arr,mid+1,right,value);
        }//如果要查询的值小于中间值，往左边查
        else if (value<arr[mid]){
            return binarySearch3(arr, left,mid-1,value);
        }//如果相等，已经找到直接返回
        else{
            tmp=mid-1;
            //此时相等的值一定在周围,从左往右
            while (true){
                if (tmp>=left&&value==arr[tmp]){
                    arrayList.add(tmp--);
                }else break;
            }
            arrayList.add(mid);
            tmp=mid+1;
            while (true){
                if (tmp<right&&value==arr[tmp]){
                    arrayList.add(tmp++);
                }else break;
            }
            return arrayList;
        }
    }
}
